/*
   (C) 2005 - Michael Ocean - Boston University

  This work is a part of the larger snBench project.  Information
  can be found at: http://csr.bu.edu/snbench

  This program is free software; you can redistribute it and/or
  modify it under the terms of Version 2 of the GNU General Public 
  License.
  
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.
  
  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free
  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/


package sxe;

import edu.bu.cs511.p5.*;
import snbenchlib.Trace;
import step.EvaluationFailure;
import step.FlowType;
import step.Graph;
import step.LastTriggerEval;
import step.Node;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.NoSuchElementException;
import snbenchlib.Log;

public class GraphEvaluatorThread extends Thread {

    boolean bRun;
    boolean bDone;
    Graph g;
    sxe.Gui gui = null;

    // CS511 START EDIT

    /** The maximum allowed concurrency */
    private static final int DEFAULT_MAX_CONCURRENCY = 5;

    /** The maximum allowed concurrency */
    private static final int DEFAULT_SXE_CONCURRENCY = 2;

    /** The system's thread manager */
    private ThreadManager threadManager;

    /** The root scheduler of the SXE */
    private IScheduler rootScheduler;

    /** The root task - it is a scheduler associated  with the rootScheduler */
    private SchedTask rootSchedTask;

    /** An associative array mapping node id's to corresponding opcode tasks */
    private Map<String, OpcodeTask> opcodeTasks = new HashMap<String, OpcodeTask>();

    /** MJO: An associate array mapping program IDs to the schedulers created at
     * their level.  E.g., the scheduler running the node with ID is actually: 
     * 		schedulerMap.get(node.ID).getParentScheduler();
     * **/
    private Map<String, SchedTask> schedulerMap = new HashMap<String,SchedTask>();
    // CS511 END EDIT

    public GraphEvaluatorThread(Graph _g, sxe.Gui gui) {
        g = _g;
        bRun = false;
        bDone = false;
        this.gui = gui;
        
        // CS511 START EDIT

        // create the thread manager to manage concurrency
        CS511Debug.debug("Creating ThreadManager");
        threadManager = SchedHierarchy.createThdManager();

        // create the root scheduler which for our
        // demonstration purposes will default to an
        // RR (round robin) scheduler
        CS511Debug.debug("Creating RRScheduler");
        //rootScheduler = new RRScheduler(DEFAULT_MAX_CONCURRENCY);
        rootScheduler = new ProportionalScheduler();
        
        // create the root task which will run the default scheduler
        CS511Debug.debug("Creating root scheduling task");
        rootSchedTask = SchedHierarchy.rootScheduler(threadManager, rootScheduler);

        Thread threadManagerThread = new Thread() {
            public void run() {
                threadManager.executeTask();
            }
        };

        threadManagerThread.start();
        // CS511 END EDIT
    }

    synchronized public boolean isDone() {
    	return bDone;
    }

    synchronized public void setDone(boolean _done) {
    	bDone = _done;
    }

    synchronized public boolean getRun() {
        return bRun;
    }

    synchronized public void Shutdown() {
        Log.evaluator.log("evaluator thread shutdown initiated", Trace.VERBOSE);
        bRun = false;
        
        //need something like this 
        g.kill_iterator();
    }

    // CS511 START EDIT
    /*
     * doSchedulerIteration -- runs over the nodes
     * and enables (from the Sched p.o.v.) those that are
     * enabled from the STEP graph p.o.v.
     * 
     * this should sleep when nothing is done ala old mech.
     */
    private void doSchedulerIteration() {
    	boolean bSomethingDoneThisPass = false;
    	
    	synchronized (opcodeTasks) {
    		// put the opcode tasks which are enabled on the ready queue of the scheduler
    	
	        for (String key : opcodeTasks.keySet()) {
	            OpcodeTask opcodeTask = opcodeTasks.get(key);
	            if (opcodeTask.getOpcode().isEnabled()) {
	                // the opcode wrapped by the task is enabled so
	                // now enable the task itself, ie, put it on the run queue
	                
	            	/* race condition madness... */
	            	opcodeTask.enableOpcode();
	                bSomethingDoneThisPass = true;
	            }
	        }
    	}
    	if(!bSomethingDoneThisPass){
    		// sleep until woken by a graft
    	}
    }
    
    public void updateSchedueForNew() {
    	if(gui!=null)
    		gui.refreshGraph();
    	updateSchedueForNewNodes();
    }
    
    /** MJO: split adding nodes to scheduler from 
     * 		enabling/evaluation	of nodes (above)
     * 
     * @requires - caller has the graph lock
     * 
     * This mechanism blindly adds all new nodes to the root
     * scheduler.  Does *not* support FlowTypes.
     * 
     * @deprecated - useful for simplified testing for code
     * 		changes
     * 
     * first check whether there are any new nodes in the graph
     * since the last time we were invoked and creating schedulable
     * opcode tasks for them.  
     * 
     * Should be called after a graft or by the node janitor after a clean up
     */
    private void updateSchedueForNewNodes() {
    	synchronized (opcodeTasks) {

			step.Node n = null;
			Iterator<step.Node> it = g.GetNodeIterator();
			while(it.hasNext()){
	    		n = it.next();

		        String nodeId = n.GetID();
		        if (!opcodeTasks.containsKey(nodeId)) {
		            CS511Debug.debug("New opcode to be added to the run queue: " + nodeId);
		            // TODO: call addSchedulers and graft to appropriate sched.
		            OpcodeTask opcodeTask = SchedHierarchy.addOpcode(rootSchedTask,new SXEOpcode(n));
		            opcodeTasks.put(nodeId, opcodeTask);
		        }
		    }
    	}
    	// wakeup bSomethingDone sleeper
    }
    
	
	/**
	 * This function adds/updates schedulers as needed for a step graph
	 *  and adds the nodes in that graph to the appropriate scheduler.
	 * 
	 * @requires - caller has the graph lock
	 * 
	 * - Performs BreadthFirstSearch to move down from the roots of the graph
	 * - Keeps last "level's" scheduler as graph is traversed
	 * - New nodes are added to closest scheduler.
	 *  
	 *  called from Server in event of Graft or by the node janitor after 
	 *  	a clean up
	 */
    private void updateSchedueForNewNodesWithFlowTypes(){
		LinkedList<Node> workQueue = new LinkedList<Node>();
		
		/* maintain a list of nodes we've visited and the SchedTask that
		 * the node's children should be added to */
		Map<String,SchedTask> visited = new HashMap<String,SchedTask>();
	
		synchronized (opcodeTasks) {
	    	for(Node n:g.getRoots()){
				/* We add this node, regardless of whether or not it's been 
				 * processesed (the "work" method we are calling is smart 
				 * enough to keep us out of double adding a node) */
				workQueue.add(n);
				visited.put(n.GetID(),rootSchedTask);
				
				while(!workQueue.isEmpty()){
					Node t = workQueue.remove();
					SchedTask stParent = visited.get(t.GetID()); 
						
					// schedule this node
					SchedTask is = schednode(t,stParent);
						
					for(Node p:t.getChildren()){
						if(!(p instanceof LastTriggerEval))
							if(!visited.containsKey(p.GetID())){
								visited.put(p.GetID(),is);
								workQueue.add(p);
							}
					}
				} 
	    	} /* end for(roots)*/
    	} /*end synch */

	}	
    
	/**
	 * In general, adds node <emph>n</emph> to the <emph>parent</emph>
	 * scheduler and checks to see if a new scheduler is defined at the
	 * level of the new node.  
	 * 		if so, that new scheduler is added and returned
	 * 		if not, the current parent is returned
	 * If n is a root, this will try to create the RR sched for the
	 * graph (unless it has already been created).
	 * 
	 * @param n - the node to check the schedule for
	 * @param parent - the SchedTask that n will be added to
	 * @return the SchedTask this node's children should be added to
	 */  
	private SchedTask schednode(Node n, SchedTask parent){
		SchedTask newST = null;
		
		/* if the node has already been scheduled, all of the below
		 * is unnecessary...
		 */
		if(opcodeTasks.containsKey(n.GetID())){
			return schedulerMap.get(n.GetID());
		}
		
		/* determine if this node is a root.  If so, add the graph scheduler
		 * (if it hasn't already been added) */
		if(n.IsOrphan()){
			if(!schedulerMap.containsKey(n.getGraphID())){
				// TODO: should check graph's flow type.  
				IScheduler schedGraph = new RRScheduler(DEFAULT_SXE_CONCURRENCY); 
			
				newST = SchedHierarchy.addScheduler(parent,schedGraph);
				schedulerMap.put(n.getGraphID(),newST);
				parent = newST;
			}
			else{
				newST=schedulerMap.get(n.getGraphID());
				parent = newST;
			}
		}
				
		// add this node to the parent
		OpcodeTask opcodeTask;

		// check node's for flowtype parameters (??)
		try{
			FlowType ft = n.getFlowType(FlowType.SCHEDULERATTRIBUTES);
			String sType = ft.getParam(FlowType.PARAM_SCHEDPRIORITY).getValue();
			// add given flowtype
			opcodeTask = SchedHierarchy.addOpcode(parent,new SXEOpcode(n),sType);
			
			Log.scheduler.log(
					"Node:" + n.GetID() + " assigned to Sched: " + parent.getScheduler().toString()  +
					" with priority (flowtype info):" + sType,
					Trace.MINIMAL);
			
		}catch(NoSuchElementException nse){
			// just add, no flowtype info avail
			opcodeTask = SchedHierarchy.addOpcode(parent,new SXEOpcode(n));
			
			Log.scheduler.log(
					"Node:" + n.GetID() + " assigned to Sched: " + parent.getScheduler().toString(),
					Trace.MINIMAL);
		}
			
		// log the addition of this flowtype
		opcodeTasks.put(n.GetID(), opcodeTask);
				
		// add another scheduler if one is present
		IScheduler t = allocateSchedulerInstanceFromFlowType(n);
		
		if(t!=null){
			// make a new schedTask for this scheduler
			try{
				SchedTask nST = SchedHierarchy.addScheduler(parent,t);
				schedulerMap.put(n.GetID(),nST);

				Log.scheduler.log(
						"Generated new Scheduler at:" + n.GetID() + " Sched: " + t.toString(),
						Trace.DEBUG);

				
				return nST;
			}catch(Exception e){
		        Log.evaluator.log("unacceptable Flow Type information for node " + n.GetID());
			}
		}
		
		return parent;
	}
	

    // CS511 END EDIT

    /* <?xml version="1.0"?>
     	<stepgraph id="wordcount">
     		<flowtype label="scheduler">
     			<param name="type" value="RoundRobin" />
     			<param name="concurrency" value="3" />
     		</flowtype>
     		<exp id="sub1" opcode="sxe.core.math.subtract">
     			<flowtype label="scheduler_settings">
     				<param name="priority" value="0" />
    	        </flowtype>
    	*/
    
	/* FlowType helper functions */
    
	/**
	 * @param n -
	 * @return - an IScheduler (e.g., RR,FP,etc) as described by
	 * the flowType on node n
	 * 
	 */
	private static IScheduler allocateSchedulerInstanceFromFlowType(Node n){
		try{
			FlowType ft = n.getFlowType(FlowType.SCHEDULER);
			String sType;
			try{
				sType = ft.getParam(FlowType.PARAM_SCHEDTYPE).getValue();
			}
			catch(NoSuchElementException nse){
				Log.scheduler.log("Could not add scheduler at Node "+ n + " as FlowType is missing " + FlowType.PARAM_SCHEDTYPE);
				return null;
			}
			int iCon;
			try{
				iCon = Integer.valueOf(ft.getParam(FlowType.PARAM_SCHEDCONCURRENCY).getValue());
			}catch(Exception e){
				// this arg isn't necessary so we ignore it.
				return SchedHierarchy.allocScheduler(sType);
			}
			
			return SchedHierarchy.allocScheduler(sType,iCon);
			
		}catch(NoSuchElementException nse){
			return null;
		}
	}
		
	protected void BFSup(Node n){
		LinkedList<Node> workQueue = new LinkedList<Node>();
		Map<String,String> visited = new HashMap<String,String>();
		
		workQueue.add(n);
		visited.put(n.GetID(),n.GetID());
		while(!workQueue.isEmpty()){
			Node t = workQueue.remove();
			if(work(t))
				return;
			for(Node p:t.getParents()){
				if(!(p instanceof LastTriggerEval))
					if(!visited.containsKey(p.GetID())){
						visited.put(p.GetID(),p.GetID());
						workQueue.add(p);
					}
			}
		}
	}	
	
	private boolean work(Node n){
		return true; //if done
	}
	   
	/**
	 * Does not return until externally quit or catastrphic
	 * failure occurs.
	 * 
	 * Pass through tree and builds a queue of nodes that 
	 * are ready (enabled) and repeatedly services that 
	 * queue until empty at which point it 
	 * repeats.  If queue is empty and can not add entries,
	 * will sleep until a graft occurs.
	 *
	 */
    public void BetterIteration(){
        Log.evaluator.log("Starting BetterIteration",Trace.VERBOSE);
        bRun = true;
        String sID = null;
        ArrayList<Node> readyQueue = g.getReadyNodes();
        
        while (getRun()) {
        	try{
        		if(readyQueue.size()==0){
        			readyQueue = g.getReadyNodes();
        		}
	        	if(readyQueue.size() == 0){
	        		g.restUntilGraft();
	        	}
	        	
	        	else{
	        		Node n = readyQueue.remove(0);
	        		/* make sure nothing changed while this was sitting in the queue */
	        		if(n==null){
	        			System.err.println("Some node was removed while in node queue");
	        			continue;
	        		}

	        		sID = n.GetID();
	        		if(!n.IsEnabled()){
	        			System.err.println("Node {" + sID + "} became disabled while in node queue");
	        			continue;
	        		}
	        		
	        		//sxe.Gui.highlightNode(sID);
	        		n.DoEvaluate();
	        		// take a break ?
	        		sleep(1);
	        		//sxe.Gui.unhighlightNode(sID);
	        	}       		
			} catch (EvaluationFailure e) {
				e.printStackTrace();
			} catch (InterruptedException ie) {
                ie.printStackTrace();
            }
        }
        Log.evaluator.log("Stopping BetterIteration",Trace.DEBUG);
        setDone(true);
    }

    public void run() {
        Log.evaluator.log("Starting GraphEvaluatorThread",Trace.VERBOSE);
        
        try{
        	BetterIteration();
        }catch(Exception e){
        	Log.evaluator.log("Exception thrown in BetterIteration but caught in run()",Trace.DEBUG);
        	Log.evaluator.printStackTrace(e);
        }
        Log.evaluator.log("Stopping GraphEvaluatorThread",Trace.DEBUG);
        setDone(true);
    }


    // CS511 START EDIT

    /**
     * A simple wrapper to tranform Graph Nodes to IOpcodes which our scheduler
     * knows how to work with
     */
    private class SXEOpcode implements IOpcode {
        private Node sxeNode;

        public SXEOpcode(Node sxeNode) {
            this.sxeNode = sxeNode;
        }

        public void execute() {
            CS511Debug.debug("execute " + sxeNode.GetID());
            try {
                sxeNode.DoEvaluate();
            } catch (EvaluationFailure evaluationFailure) {
                sxeNode.markAsGarbage();
                evaluationFailure.printStackTrace();
            }
        }

        public boolean isEnabled() {
            return sxeNode.IsEnabled();
        }

        public Node getSxeNode() {
            return sxeNode;
        }
    }
    // CS511 END EDIT

    /**
     *  @requires - caller has the graph lock
     *  @param - prunedNodes - the nodes that have been removed from the graph
     *  
     *  Remove the nodes from the opcodeTasks map.
     *  
     *  @deprecated - does not deal with schedulers/flowtypes
     */
    public void updateSchedueForNodeDeletion(ArrayList<String> prunedNodes) {
		synchronized (opcodeTasks) {
			Log.scheduler.log("updateSchedueForNodeDeletion",
					Trace.VERBOSE);
	    	for(String s: prunedNodes){
	    		if(opcodeTasks.containsKey(s)){
	    			/* remove the task from the list */
	    			OpcodeTask opcode = opcodeTasks.remove(s);

	    			Log.scheduler.log("removing opcode associated with task id " + s,
	    					Trace.DEBUG);
	    			
	    			opcode.endTask();

	    			Log.scheduler.log("opcode.endTask called on task id " + s,
	    					Trace.DEBUG);

	    			// clean up Scheduler/Map as needed
	    		}
	    	}			
    	}
    	//maybe wakeup bSomethingDone sleeper(?)
	}
}
